﻿#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
using namespace std;

//双指针：1.移动零
class Solution1 {
public:
    void moveZeroes(vector<int>& nums) 
    {
        int cur=0;
        int dest=-1;
        for(cur,dest;cur<nums.size();cur++)
        {
            if(nums[cur])
                swap(nums[++dest],nums[cur]);
        }
    }
};
void test1()
{
    Solution1 A;
    vector<int> nums;
    nums.push_back(0);
    nums.push_back(1);
    nums.push_back(0);
    nums.push_back(3);
    nums.push_back(12);
    A.moveZeroes(nums);
    for (int i = 0; i < nums.size(); i++)
    {
        cout << nums[i] << ' ';
    }
    cout << endl;
}
//双指针：2.复写零，o(n²)算法 
//class solution2 {
//public:
//    void duplicatezeros(vector<int>& arr) 
//    {
//        int cur=0;
//        int dest=0;
//        int size=arr.size();
//        for(cur;cur<size;cur++)
//        {
//            if(arr[cur]==0&&cur!=size-1)
//            {
//                for(dest=size-1;dest>cur+1;dest--)
//                {
//                    arr[dest]=arr[dest-1];
//                }
//                arr[++cur]=0;
//            }
//        } 
//    }
//};

//双指针：2.复写零，o(n)算法 
class Solution2 {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int cur=0;
        int dest=-1;
        int size=arr.size();
        while(cur<size)
        {
            if(arr[cur])
            {
                dest++;
            }
            else
            {
                dest+=2;
            }
            if(dest>=size-1)
                break;
            cur++;            
        }
        if(dest==size)
        {
            arr[size-1]=0;
            cur--;
            dest-=2;
        }
        while(cur>=0)
        {
            if(arr[cur])
            {
                arr[dest--]=arr[cur--];                
            }
            else
            {
                arr[dest--]=arr[cur];
                arr[dest--]=arr[cur];
                cur--;
            }
        }
    }
};

void test2()
{
    Solution2 A;
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(0);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(0);
    nums.push_back(4);
    nums.push_back(5);
    nums.push_back(0);
    A.duplicateZeros(nums);
    for (int i = 0; i < nums.size(); i++)
    {
        cout << nums[i] << ' ';
    }
    cout << endl;
}


//双指针：3.快乐数
class Solution3 {
public:
    bool isHappy(int n) 
    {
        if(n==1)
            return true;
        int quick = isHappy_(n);
        int slow = n;       
        while(quick!=slow)
        {
            quick = isHappy_(isHappy_(quick));
            slow = isHappy_(slow);
        }
        return slow==1;
    }

    int isHappy_(int n)
    {
        int ret=0;
        while(n!=0)
        {
            ret+=(n%10)*(n%10);
            n/=10;
        }
        return ret;
    }
};

void test3()
{
    Solution3 A;
    A.isHappy(19);
}

//双指针：4.盛最多水的容器
class Solution4 {
public:
    int maxArea(vector<int>& height) 
    {
        int size=height.size();
        int left=0;
        int right=size-1;
        int max=0;
        int volume=0;
        while(left!=right)
        {
            volume=(height[left]>height[right]?height[right]:height[left])*(right-left);
            max=(max>volume?max:volume);
            if(height[left]>height[right])
                right--;
            else
                left++;
        }
        return max;
    }
};

void test4()
{
    Solution4 A;
    vector<int> arr = { 1,8,6,2,5,4,8,3,7 };    
    cout << A.maxArea(arr) << endl;
}

int main()
{
    //test1();
    //test2();
    //test3();
    test4();
    return 0;
}

